/*
题目：从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
public class BuildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Stack<TreeNode> stack = new Stack<> ();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);//先压入根节点
        int inorderIndex = 0;//用于遍历中序数组

        for (int i = 1; i < preorder.length; i++) {
            TreeNode tmp = stack.peek();
            if (tmp.val != inorder[inorderIndex]) {
                tmp.left = new TreeNode(preorder[i]);
                stack.push(tmp.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    tmp = stack.pop();
                    inorderIndex++;
                }
                tmp.right = new TreeNode(preorder[i]);
                stack.push(tmp.right);
            }
        }

        return root;
    }
}
